#include <iostream>
#include <unordered_set>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

/*
一个非常直观的思路是：我们遍历链表中的每个节点，并将它记录下来；
一旦遇到了此前遍历过的节点，就可以判定链表中存在环。
借助哈希表可以很方便地实现。
*/
class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        unordered_set<ListNode*> visted;
        while (head != nullptr) {
            // if (visted.count(head))
            if (visted.find(head) != visted.end()) {
                return head;
            }

            visted.insert(head);

            head = head->next;
        }

        return nullptr;
    }
};

int main() {
    ListNode* head = new ListNode(3);

    cout << Solution().detectCycle(head) << endl;

    return 0;
}